/**
 * 
 */
package array;

import utils.CreateUtils;
import utils.PrintUtils;

/**
 * @author Michael
 *set Matrix Zeros
 * Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
 * space O(1)? O(m+n)
 */
public class SetMatrixZeros {

	public static int[][] setMartxZeors(int[][] arr){
		assert (arr != null);
		boolean is1stRowZero = false;
		boolean is1stColZero = false;
		
		//check 1st row
		for (int i = 0; i < arr[0].length; ++i) {
			if (arr[0][i] == 0) {
				is1stRowZero = true;
				break;
			}
		}
		
		//check 1st col
		for (int i = 0; i < arr.length; ++i) {
			if (arr[i][0] == 0) {
				is1stColZero = true;
				break;
			}
		}
		
		for (int row = 1; row < arr.length; ++row) {
			for (int col = 1; col < arr[0].length; ++col) {
				if (arr[row][col] == 0) {
					arr[row][0] = 0;
					arr[0][col] = 0;
				}
			}
		}
		
		// set 0 for each row
		for (int row = 1; row < arr.length; ++row) {
			if (arr[row][0] == 0) {
				for (int col = 1; col < arr[row].length; ++col) {
					arr[row][col] = 0;
				}
			}
		}

		// set 0 for each col
		for (int col = 1; col < arr[0].length; ++col) {
			if (arr[0][col] == 0) {
				for (int row = 1; row < arr.length; ++row) {
					arr[row][col] = 0;
				}
			}
		}

		if (is1stRowZero) {
			for (int col = 0; col < arr[0].length; ++col) {
				arr[0][col] = 0;
			}
		}
		
		if (is1stColZero) {
			for (int row = 1; row < arr.length; ++row) {
				arr[row][0] = 0;
			}
		}
		
		return arr;
	}
	
	/**
	 * 
	 */
	public SetMatrixZeros() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] m = CreateUtils.randNonNegMatrix(10, 2, false);
		PrintUtils.print2DArray(m);
		System.out.println();
		PrintUtils.print2DArray(setMartxZeors(m));

	}

}
